package com.zwj.interview.BFS;

/**
 * 一棵二叉树的所有节点的值要么是0要么是1，请剪除该二叉树中所有节点的值全都是0的子树
 */
public class 剪除二叉树中所有节点的值全都是0的子树 {

    /**
     *
     * 剪枝：
     * 首先，这个节点的值应该是0。其次，如果它有子树，那么它的子树的所有节点的值都为0。
     * 也就是说，如果一个节点可以被删除，那么它的子树的所有节点都可以被删除
     * <p>
     * 后序遍历最适合用来解决这个问题。如果用后序遍历的顺序遍历到某个节点，
     * 那么它的左右子树的节点一定已经遍历过了。每遍历到一个节点，就要确定它是否有左右子树，
     * 如果左右子树都是空的，并且节点的值是0，那么也就可以删除这个节点
     *
     * @param root
     * @return 实质上是实现了递归的后序遍历。每当遍历到一个节点，如果该节点符合条件，则将该节点删除。
     * 由于是后序遍历，因此先对根节点root的左右子树递归调用函数pruneTree删除左右子树中节点值全是0的子树。
     * 。所谓删除一个节点，就是返回null给它的父节点，
     * 这样这个节点就从这棵二叉树中消失
     */
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        //要求所有所有节点都为0的子树，说明所有节点都走完了，那么这里后序遍历最为合适
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        //只有当root的左右子树全部为空，并且它自己的值也是0时，这个节点才能被删除
        if (root.left == null && root.right == null && root.val == 0) {
            return null;
        }
        //上面返回null，就是删除节点了
        return root;
    }




}
